package algorithms.leaning.class13;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * 给定一棵二叉树的头节点head，
 * 返回这颗二叉树中最大的二叉搜索子树的头节点
 *
 * @author guichang
 * @date 2021/6/13
 */

@SuppressWarnings("all")
public class Code1_二叉树_最大二叉搜索子树头节点 {
    // algorithms.leaning.class12.Code6_二叉树_最大二叉搜索子树大小
    // 上提基础上Info里加个头节点

    public static void main(String[] args) {
        TreeNode head = MyUtil.createTreeNode(6, 5, 8, 4, null, 7, 9);
        MyUtil.print(maxBSTNode(head).val); // 7
    }

    public static TreeNode maxBSTNode(TreeNode head) {
        return process(head).maxBSTHead;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(null, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
        }
        Info tl = process(node.left);
        Info tr = process(node.right);
        int size = tl.size + tr.size + 1;
        int max = Math.max(Math.max(tl.max, tr.max), node.val);
        int min = Math.min(Math.min(tl.min, tr.min), node.val);
        // 先判断不经过x的情况
        TreeNode maxBSTHead = tl.maxBSTHead;
        int maxBSTSize = tl.maxBSTSize;
        if (maxBSTSize < tr.maxBSTSize) {
            maxBSTSize = tr.maxBSTSize;
            maxBSTHead = tr.maxBSTHead;
        }
        // 能否经过x，maxBSTSize == size表示这颗树是BST
        boolean tlIsBST = tl.maxBSTSize == tl.size;
        boolean trIsBST = tr.maxBSTSize == tr.size;
        if (tlIsBST && trIsBST && tl.max < node.val && tr.min > node.val) {
            // 整棵树都是BST的话毫无疑问最大值就是node了
            maxBSTSize = size;
            maxBSTHead = node;
        }
        return new Info(maxBSTHead, maxBSTSize, max, min, size);

    }

    private static class Info {
        TreeNode maxBSTHead; // 最大的头结点
        int maxBSTSize; // 最大的节点数
        int max; // 最大值
        int min; // 最小值
        int size; // 总数

        public Info(TreeNode maxBSTHead, int maxBSTSize, int max, int min, int size) {
            this.maxBSTHead = maxBSTHead;
            this.maxBSTSize = maxBSTSize;
            this.max = max;
            this.min = min;
            this.size = size;
        }
    }


}